package com.hjx.leetcode;

/**
 *
 */
class LeetCode_21 {

    /**
     * 两个链表中第一项更小的头结点作为第一项，剩余项组成的链表和另一个链表递归合并
     * {
     *   l1[0] + mergeTwoLists(l1[1:], l2) (l1[0] < l2[0])
     *   l2[0] + mergeTwoLists(l1, l2[1:]) (l1[0] >= l2[0])
     * }
     * @param l1
     * @param l2
     * @return
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val >= l2.val) {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        } else {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
    }

    public static void main(String[] args) {
        ListNode n1 = new ListNode(1);
        ListNode n3 = new ListNode(3);
        ListNode n5 = new ListNode(5);
        ListNode n7 = new ListNode(7);
        ListNode n9 = new ListNode(9);
        ListNode n2 = new ListNode(2);
        ListNode n4 = new ListNode(4);
        ListNode n6 = new ListNode(6);
        ListNode n8 = new ListNode(8);
        ListNode n10 = new ListNode(10);

        n1.next = n3;
        n3.next = n5;
        n5.next = n7;
        n7.next = n9;

        n2.next = n4;
        n4.next = n6;
        n6.next = n8;
        n8.next = n10;


        ListNode newListNode = new LeetCode_21().mergeTwoLists(n1, n2);
        while (newListNode != null) {
            System.out.print(newListNode.val + " ");
            newListNode = newListNode.next;
        }
    }
}

